package dp.最大字段和;

public class Test {
    public static void main(String[] args) {
        // 求下面数组的最大字段和
        //int[] arr = {1, 4, 5, 6, -2, 1, 3, 6};
        int[] arr = {-2, 11, -4, 13, -5, -2};

        // 1. 创建 dp 表 ： dp[i] 表示i位置为结尾的最大字段和
        int[] dp = new int[arr.length];

        // 2. 初始化
        dp[0] = arr[0];

        // 3. 填表和找最大的
        int max = 0;
        for (int i = 1; i < arr.length; i++) {
            dp[i] = Math.max(dp[i-1] + arr[i], arr[i]);
            max = Math.max(max, dp[i]);
        }

        System.out.println("最大子数组和为: " + max);
    }
}
